package com.zhhe.algorithm;

/**
 * 裴波那契数列实现
 */
public class Fibonacci {

    public static void main(String[] args) {
        //1、常规实现
        int[] array = new int[20];
        array[0] = 0;
        array[1] = 1;
        for (int i = 2; i < array.length; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        System.out.println("normal:");
        for (int i:array){
            System.out.print(i + " ");
        }

        //2、递归实现
        int[] fbiArray = new int[20];
        for (int i = 0; i < fbiArray.length; i++) {
            fbiArray[i] = fbi(i);
        }
        System.out.println();
        System.out.println("fbi:");
        for (int i:fbiArray){
            System.out.print(i + " ");
        }
    }

    /**
     * 递归函数
     * @param i
     * @return
     */
    public static int fbi(int i) {
        if (i < 2) {
            return i == 0 ? 0 : 1;
        }
        return fbi(i -1) + fbi(i - 2);
    }
}
